from utils import ListNode


class ChainSolution:
    """some algorithms in chains."""

    def find_first_common_node(self, root1, root2):
        """find_first_common_node in two chains.

        Args:
            root1: the root ListNode of the first linked list.
            root2: the root ListNode of the second linked list.
        """
        if root1 == root2:
            return root1
        if root1 == None or root2 == None:
            return None
        origin_root1 = root1
        origin_root2 = root2

        while root1 != root2:
            root1 = root1.next if root1 else origin_root2
            root2 = root2.next if root2 else origin_root1

        return root1

    def reverse_list(self, root1):
        """reverse a linked list.

        Args:
            root1: the root ListNode in the linked list.
        """
        prev = None
        while root1:
            next_node = root1.next
            root1.next = prev
            prev = root1
            root1 = next_node
        return prev

    #  def print_chains(self, root1):
    #      """print values sequently in the chains.
    #
    #      Args:
    #          root1: the root ListNode.
    #      """
    #      while root1 != None:
    #          print(root1.val, end=" ")
    #          root1 = root1.next
    #      print("")

    def merge_two_sorted_chains(self, root1, root2):
        """merge_two_sorted_chains, non-recursive method.

        Args:
            root1:
            root2:
        """
        dummy_root = ListNode(0)
        record = dummy_root
        while root1 and root2:
            if root1.val <= root2.val:
                dummy_root.next = root1
                root1 = root1.next
            else:
                dummy_root.next = root2
                root2 = root2.next
            dummy_root = dummy_root.next
        dummy_root.next = root1 if root1 else root2
        return record.next

    def is_palindrom(self, root):
        """is_palindrom.

        use slow andd fast pointer to find center of the chain, thus
        reverse the right half chain, compare the reversed chain with
        normal linked list.

        Args:
            root:
        """

        if not root or not root.next:
            return False
        slow = root
        fast = root
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = self.reverse_list(slow.next)
        slow = slow.next

        while slow:
            if slow.val != root.val:
                return False
            slow = slow.next
            root = root.next
        return True

    def odd_even_list(self, root):
        """odd_even_list,维护奇数偶数两个链表，最后拼接.

        Args:
            root:
        """
        if not root:
            return root

        even_head = root.next
        odd, even = root, even_head
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return root

    def remove_nth_from_end(self, root, n):
        """remove_nth_from_end,设置一个哑节点，减少判断.

        Args:
            root:
            n:
        """
        dummy = ListNode(0)
        dummy.next = root
        fast = root
        slow = dummy

        for i in range(n):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next


def main():
    p1 = ListNode(1)
    p2 = ListNode(2)
    p3 = ListNode(3)
    p4 = ListNode(4)
    p5 = ListNode(5)
    p6 = ListNode(6)

    p1.next = p2
    p2.next = p3
    p3.next = p4
    p4.next = p5

    a = ChainSolution()
    print(p1)
    p1 = a.remove_nth_from_end(p1, 2)

    print(p1)


if __name__ == "__main__":
    main()
